<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            给定一个字符串s，将s分割成子串，这就是切割类问题类似于组合，也是需要回溯
            从abcde 先选取a，然后第二层从bcde中选
            从abcde先切割a，然后第二层从bcde中切割

            ①确定终止条件。当s被切割完了即终止，每次需要确定一个startIndex，来判断从哪里开始切，因此
            终止条件可以为 if(startIndex==s.length) return

            ②for循环遍历条件。首先需要确定集合，从startIndex开始，逐个裁剪到字符串结束，裁剪出来如果是回文，才推入path
            进入下一层递归，如果不是，就continue。

            问题在于，没有剪枝，第一层     a|bcde                  ab|cde abc|de abcd|e abcde
                              第二层  b|cde   bc|de  bcd|e  bcde   
            但貌似也不需要剪枝      
            */
            var partition = function (s) {
                let res = []
                function backTracking(path, startIndex) {
                    if (startIndex == s.length) {
                        return res.push([...path])
                    }
                    for (let i = startIndex; i < s.length; i++) {
                        let str = s.slice(startIndex, i + 1)
                        if (isPali(str)) {
                            path.push(str)
                            backTracking(path, i + 1)
                            path.pop()
                        }
                    }
                }
                backTracking([], 0)
                return res
                function isPali(str) {
                    let left = 0
                    let right = str.length - 1
                    while (left <= right) {
                        if (str[left] != str[right]) {
                            return false
                        }
                        left++
                        right--
                    }
                    return true
                }
            }
        </script>
    </body>
</html>
